package com.computer.fundamentals.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 滑动窗口思想：
 *      将子数组（子字符串）理解成一个滑动的窗口，然后将这个窗口在数组上滑动，
 *      在窗口滑动的过程中，左边会出一个元素，右边会进一个元素，然后只需要计算当前窗口内的元素值即可。
 */
public class SlidingWindows {

    /**
     * 以经典问题——无重复字符的最长子串为例(LeetCode.3):
     *      给定一个字符串(由字母、数字、符号及空格组成)，请你找出其中不含有重复字符的 最长子串 的长度。
     */
    public int lengthOfLongestSubstring(String str) {
        Map<Character, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0, j = 0;j < str.length();j++) {
            if (!map.containsKey(str.charAt(j))) {
                map.put(str.charAt(j), 1);
            }else {
                while (i < j && str.charAt(i) != str.charAt(j)) {
                    map.remove(str.charAt(i));
                    i++;
                }
                i++;
            }
            res = Math.max(j-i+1, res);
        }

        return res;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        SlidingWindows slidingWindows = new SlidingWindows();
        System.out.println("------------滑动窗口测试------------");
        int length = slidingWindows.lengthOfLongestSubstring("abcabcbb");
        System.out.println(length);

    }
}